package puf.m2.automaton.converter;
//
//import OneWay;
//import FSATransition;
//import FiniteStateTwoWay;
//import State;
//import StatePlacer;
//import Transition;
//import gui.environment.Universe;
import java.util.ArrayList;

import puf.m2.automaton.Automaton;
import puf.m2.automaton.State;
import puf.m2.automaton.Transition;
import puf.m2.regular.*;
public class OneWayFAToREConverter {

    /**
     * Returns true if <CODE>automaton</CODE> can be converted to a regular
     * expression (i.e. it has a unique initial and final state and it is a
     * finite state automaton, and the initial state is not the final state).
     *
     * @param automaton
     *            the automaton to convert
     * @return true if <CODE>automaton</CODE> can be converted to a regular
     *         expression.
     */
public static boolean isConvertable(Automaton automaton) {
//		if (!(automaton instanceof FiniteStateTwoWay))
//			return false;
        State[] finalStates = automaton.getFinalStates();
        if (finalStates.length != 1) {
            return false;
        }

        State initialState = automaton.getInitialState();
        if (finalStates[0] == initialState) {
            return false;
        }
        return true;
    }

    /**
     * Returns true if there are more removable states in <CODE>automaton</CODE>.
     *
     * @param automaton
     *            the automaton
     * @return true if there are more removable states in <CODE>automaton</CODE>.
     */
public static boolean areRemovableStates(Automaton automaton) {
        State[] states = automaton.getStates();
        for (int k = 0; k < states.length; k++) {
            if (isRemovable(states[k], automaton))
                return true;
        }
        return false;
    }

    /**
     * Returns true if <CODE>state</CODE> is a removable state (i.e. it is not
     * the unique initial or final state).
     *
     * @param state
     *            the state to remove.
     * @param automaton
     *            the automaton.
     * @return true if <CODE>state</CODE> is a removable state
     */
public static boolean isRemovable(State state, Automaton automaton) {
        State[] finalStates = automaton.getFinalStates();
        State finalState = finalStates[0];
        State initialState = automaton.getInitialState();
        if (state == finalState || state == initialState)
            return false;
        return true;
    }

    /**
     * Returns a Transition object that represents the transition between the
     * states with ID's <CODE>p</CODE> and <CODE>q</CODE>, with <CODE>expression</CODE>
     * as the transition label.
     *
     * @param p
     *            the ID of the from state.
     * @param q
     *            the ID of the to state.
     * @param expression
     *            the expression
     * @param automaton
     *            the automaton
     * @return a Transition object that represents the transition between the
     *         states with ID's <CODE>p</CODE> and <CODE>q</CODE>, with
     *         <CODE>expression</CODE> as the transition label.
     */
public static Transition getTransitionForExpression(int p, int q,
            String expression, Automaton automaton) {
        State fromState = automaton.getStateWithID(p);
        State toState = automaton.getStateWithID(q);
        Transition transition = new Transition(fromState, toState,
                expression,null);
        return transition;
    }

    /**
     * Returns the expression on the transition between <CODE>fromState</CODE>
     * and <CODE>toState</CODE> in <CODE>automaton</CODE>.
     *
     * @param fromState
     *            the from state
     * @param toState
     *            the to state
     * @param automaton
     *            the automaton
     * @return the expression on the transition between <CODE>fromState</CODE>
     *         and <CODE>toState</CODE> in <CODE>automaton</CODE>.
     */
    public static String getExpressionBetweenStates(State fromState, State toState,
            Automaton automaton) {
        Transition[] transitions = automaton.getTransitionsFromStateToState(
                fromState, toState);
        Transition trans =  transitions[0];
        return trans.label();
    }

    /**
     * Returns the expression obtained from evaluating the following equation:
     * r(pq) = r(pq) + r(pk)r(kk)*r(kq), where p, q, and k represent the IDs of
     * states in <CODE>automaton</CODE>.
     *
     * @param p
     *            the from state
     * @param q
     *            the to state
     * @param k
     *            the state being removed.
     * @param automaton
     *            the automaton.
     * @return the expression obtained from evaluating the following equation:
     *         r(pq) = r(pq) + r(pk)r(kk)*r(kq), where p, q, and k represent the
     *         IDs of states in <CODE>automaton</CODE>.
     */
    public static String getExpression(int p, int q, int k, Automaton automaton) {
        State fromState = automaton.getStateWithID(p);
        State toState = automaton.getStateWithID(q);
        State removeState = automaton.getStateWithID(k);

        String pq = getExpressionBetweenStates(fromState, toState, automaton);
        String pk = getExpressionBetweenStates(fromState, removeState,
                automaton);
        String kk = getExpressionBetweenStates(removeState, removeState,
                automaton);
        String kq = getExpressionBetweenStates(removeState, toState, automaton);

        String temp1 = star(kk);
        String temp2 = concatenate(pk, temp1);
        String temp3 = concatenate(temp2, kq);
        String label = or(pq, temp3);
        return label;
    }

    /**
     * Returns the expression that represents <CODE>r1</CODE> concatenated
     * with <CODE>r2</CODE>. (essentialy just the two strings concatenated).
     *
     * @param r1
     *            the first part of the expression.
     * @param r2
     *            the second part of the expression.
     * @return the expression that represents <CODE>r1</CODE> concatenated
     *         with <CODE>r2</CODE>. (essentialy just the two strings
     *         concatenated).
     */
    public static String concatenate(String r1, String r2) {
        if (r1.equals(EMPTY) || r2.equals(EMPTY))
            return EMPTY;
        else if (r1.equals(LAMBDA))
            return r2;
        else if (r2.equals(LAMBDA))
            return r1;
        if (Discretizer.or(r1).length > 1)
            r1 = addParen(r1);
        if (Discretizer.or(r2).length > 1)
            r2 = addParen(r2);
        return r1 + r2;
    }

    /**
     * Returns the expression that represents <CODE>r1</CODE> kleene-starred.
     *
     * @param r1
     *            the expression being kleene-starred.
     * @return the expression that represents <CODE>r1</CODE> kleene-starred.
     */
    public static String star(String r1) {
        if (r1.equals(EMPTY) || r1.equals(LAMBDA))
            return LAMBDA;
        if (Discretizer.or(r1).length > 1 || Discretizer.cat(r1).length > 1) {
            r1 = addParen(r1);
        } else {
            if (r1.endsWith(KLEENE_STAR))
                return r1;
        }
        return r1 + KLEENE_STAR;
    }

    /**
     * Returns the string that represents <CODE>r1</CODE> or'ed with <CODE>r2</CODE>.
     *
     * @param r1
     *            the first expression
     * @param r2
     *            the second expression
     * @return the string that represents <CODE>r1</CODE> or'ed with <CODE>r2</CODE>.
     */
    public static String or(String r1, String r2) {
        if (r1.equals(EMPTY))
            return r2;
        if (r2.equals(EMPTY))
            return r1;
        if (r1.equals(LAMBDA) && r2.equals(LAMBDA))
            return LAMBDA;
        if (r1.equals(LAMBDA))
            r1 = LAMBDA_DISPLAY;
        if (r2.equals(LAMBDA))
            r2 = LAMBDA_DISPLAY;
        // if(needsParens(r1)) r1 = addParen(r1);
        // if(needsParens(r2)) r2 = addParen(r2);
        return r1 + OR + r2;
    }

    /**
     * Completely reconstructs <CODE>automaton</CODE>, removing all
     * transitions and <CODE>state</CODE> and adding all transitions in <CODE>transitions</CODE>.
     *
     * @param state
     *            the state to remove.
     * @param transitions
     *            the transitions returned for removing <CODE>state</CODE>.
     * @param automaton
     *            the automaton.
     */
    public static void removeState(State state, Transition[] transitions,
            Automaton automaton) {
        Transition[] oldTransitions = automaton.getTransitions();
        for (int k = 0; k < oldTransitions.length; k++) {
            automaton.removeTransition(oldTransitions[k]);
        }

        automaton.removeState(state);

        for (int i = 0; i < transitions.length; i++) {
            automaton.addTransition(transitions[i]);
        }
    }

    /**
     * Returns a list of all transitions for <CODE>automaton</CODE> created by
     * removing <CODE>state</CODE>.
     *
     * @param state
     *            the state to remove.
     * @param automaton
     *            the automaton.
     * @return a list of all transitions for <CODE>automaton</CODE> created by
     *         removing <CODE>state</CODE>.
     */
public static Transition[] getTransitionsForRemoveState(State state,
            Automaton automaton) {
        if (!isRemovable(state, automaton))
            return null;
        ArrayList list = new ArrayList();
        int k = state.id();
        State[] states = automaton.getStates();
        for (int i = 0; i < states.length; i++) {
            int p = states[i].id();
            if (p != k) {
                for (int j = 0; j < states.length; j++) {
                    int q = states[j].id();
                    if (q != k) {
                        String exp = getExpression(p, q, k, automaton);
                        list.add(getTransitionForExpression(p, q, exp,
                                automaton));
                    }
                }
            }
        }
        return (Transition[]) list.toArray(new Transition[0]);
    }

    /**
     * Adds a new transition to <CODE>automaton</CODE> between <CODE>fromState</CODE>
     * and </CODE>toState</CODE> on the symbol for the empty set.
     *
     * @param fromState
     *            the from state for the transition
     * @param toState
     *            the to state for the transition
     * @param automaton
     *            the automaton.
     * @return the <CODE>FSATransition</CODE> that was created
     */
    public static Transition addTransitionOnEmptySet(State fromState,
            State toState, Automaton automaton) {
        Transition t = new Transition(fromState, toState, EMPTY,null);
        automaton.addTransition(t);
        return t;
    }

    /**
     * Removes all transitions in <CODE>transitions</CODE> from <CODE>automaton</CODE>,
     * replacing them with a single transition in <CODE>automaton</CODE>
     * between <CODE>fromState</CODE> and <CODE>toState</CODE> labeled with
     * a regular expression that represents the labels of all the removed
     * transitions Or'ed together (e.g. a + (b*c) + (d+e)).
     *
     * @param fromState
     *            the from state for <CODE>transitions</CODE> and for the
     *            newly created transition.
     * @param toState
     *            the to state for <CODE>transitions</CODE> and for the newly
     *            created transition.
     * @param transitions
     *            the transitions being removed and combined into a single
     *            transition
     * @param automaton
     *            the automaton
     * @return the transition that replaced all of these
     */
    public static Transition combineToSingleTransition(State fromState,
            State toState, Transition[] transitions, Automaton automaton) {
        String label = "";
        automaton.removeTransition(transitions[0]);
        for (int i = 1; i < transitions.length; i++) {
            label = or(label, "");
            automaton.removeTransition(transitions[i]);
        }
        Transition t = new Transition(fromState, toState, label,null);
        automaton.addTransition(t);
        return t;
    }

    /**
     * Makes all final states in <CODE>automaton</CODE> non-final, adding
     * transitions from these states to a newly created final state on lambda.
     *
     * @param automaton
     *            the automaton
     */
    public static void getSingleFinalState(Automaton automaton) {
        State finalState = automaton.createState();

        State[] finalStates = automaton.getFinalStates();
        for (int k = 0; k < finalStates.length; k++) {
            State state = finalStates[k];
            automaton
                    .addTransition(new Transition(state, finalState, LAMBDA,null));
            automaton.removeFinalState(state);
        }
        automaton.addFinalState(finalState);
    }

    /**
     * Converts <CODE>automaton</CODE> to an equivalent automaton with a
     * single transition between all combinations of states. (if there are
     * currently more than one transition between two states, it combines them
     * into a single transition by or'ing the labels of all the transitions. If
     * there is no transition between two states, it creates a transition and
     * labels it with the empty set character (EMPTY).
     *
     * @param automaton
     *            the automaton.
     */
public static void convertToSimpleTwoWay(Automaton automaton) {
        if (!isConvertable(automaton))
            getSingleFinalState(automaton);
        State[] states = automaton.getStates();
        for (int k = 0; k < states.length; k++) {
            for (int j = 0; j < states.length; j++) {
                Transition[] transitions = automaton
                        .getTransitionsFromStateToState(states[k], states[j]);
                if (transitions.length == 0) {
                    addTransitionOnEmptySet(states[k], states[j], automaton);
                }
                if (transitions.length > 1) {
                    combineToSingleTransition(states[k], states[j],
                            transitions, automaton);
                }
            }
        }
    }

    /**
     * Converts <CODE>automaton</CODE> into a generalized transition graph
     * with only two states, a unique initial state, and a unique final state.
     *
     * @param automaton
     *            the automaton.
     */
public static void convertToGTG(Automaton automaton) {
        State[] finalStates = automaton.getFinalStates();
        State finalState = finalStates[0];
        State initialState = automaton.getInitialState();
        State[] states = automaton.getStates();
        for (int k = 0; k < states.length; k++) {
            State state = states[k];
            if (state != finalState && state != initialState) {
                Transition[] transitions = getTransitionsForRemoveState(state,
                        automaton);
                removeState(state, transitions, automaton);
            }
        }
    }

    /**
     * Returns true if <CODE>word</CODE> is one character long and it is a
     * letter.
     *
     * @param word
     *            the word
     * @return true if <CODE>word</CODE> is one character long and it is a
     *         letter.
     */
public static boolean isSingleCharacter(String word) {
        if (word.length() != 1)
            return false;
        char ch = word.charAt(0);
        return  java.lang.Character.isLetter( ch);


    }

    /**
     * Returns true if <CODE>word</CODE> needs parens. (i.e. it is an '+' (OR)
     * expression)
     *
     * @param word
     *            the word.
     * @return true if <CODE>word</CODE> needs parens. (i.e. it is an '+' (OR)
     *         expression)
     */
public static boolean needsParens(String word) {
        for (int k = 0; k < word.length(); k++) {
            char ch = word.charAt(k);
            if (ch == '+')
                return true;
        }
        return false;
    }

    /**
     * Returns a string of <CODE>word</CODE> surrounded by parentheses. i.e. (<word>),
     * unless it is unnecessary.
     *
     * @param word
     *            the word.
     * @return a string of <CODE>word</CODE> surrounded by parentheses.
     */
public static String addParen(String word) {
        return LEFT_PAREN + word + RIGHT_PAREN;
    }

    /**
     * Returns a non-unicoded version of <CODE>word</CODE> for debug purposes.
     *
     * @param word
     *            the expression to output
     * @return a non-unicoded version of <CODE>word</CODE> for debug purposes.
     */
public static String getExp(String word) {
        if (word.equals(LAMBDA))
            return "lambda";
        else if (word.equals(EMPTY))
            return "empty";
        return word;
    }

    /**
     * Returns the expression for the values of ii, ij, jj, and ji determined
     * from the GTG with a unique initial and final state.
     *
     * @param ii
     *            the expression on the loop off the initial state
     * @param ij
     *            the expression on the arc from the initial state to the final
     *            state.
     * @param jj
     *            the expression on the loop off the final state.
     * @param ji
     *            the expression on the arc from the final state to the initial
     *            state.
     * @return the expression for the values of ii, ij, jj, and ji determined
     *         from the GTG with a unique initial and final state.
     */
public static String getFinalExpression(String ii, String ij, String jj, String ji) {
        String temp = concatenate(star(ii), concatenate(ij, concatenate(
                star(jj), ji)));
        String temp2 = concatenate(star(ii), concatenate(ij, star(jj)));
        // String expression =
        // concatenate(star(concatenate(LEFT_PAREN,concatenate(temp,RIGHT_PAREN))),
        // temp2);
        String expression = concatenate(star(temp), temp2);
        return expression;
    }

    /**
     * Returns the expression on the loop off the initial state of <CODE>automaton</CODE>.
     *
     * @param automaton
     *            a generalized transition graph with only two states, a unique
     *            initial and final state.
     * @return the expression on the loop off the initial state of <CODE>automaton</CODE>.
     */
public static String getII(Automaton automaton) {
        State initialState = automaton.getInitialState();
        return getExpressionBetweenStates(initialState, initialState, automaton);
    }

    /**
     * Returns the expression on the arc from the initial state to the final
     * state of <CODE>automaton</CODE>.
     *
     * @param automaton
     *            a generalized transition graph with only two states, a unique
     *            initial and final state.
     * @return the expression on the arc from the initial state to the final
     *         state of <CODE>automaton</CODE>.
     */
public static String getIJ(Automaton automaton) {
        State initialState = automaton.getInitialState();
        State[] finalStates = automaton.getFinalStates();
        State finalState = finalStates[0];
        return getExpressionBetweenStates(initialState, finalState, automaton);
    }

    /**
     * Returns the expression on the loop off the final state of <CODE>automaton</CODE>
     *
     * @param automaton
     *            a generalized transition graph with only two states, a unique
     *            initial and final state.
     * @return the expression on the loop off the final state of <CODE>automaton</CODE>
     */
public static String getJJ(Automaton automaton) {
        State[] finalStates = automaton.getFinalStates();
        State finalState = finalStates[0];
        return getExpressionBetweenStates(finalState, finalState, automaton);
    }

    /**
     * Returns the expression on the arc from the final state to the initial
     * state of <CODE>automaton</CODE>
     *
     * @param automaton
     *            a generalized transition graph with only two states, a unique
     *            initial and final state.
     * @return the expression on the arc from the final state to the initial
     *         state of <CODE>automaton</CODE>
     */
public static String getJI(Automaton automaton) {
        State initialState = automaton.getInitialState();
        State[] finalStates = automaton.getFinalStates();
        State finalState = finalStates[0];
        return getExpressionBetweenStates(finalState, initialState, automaton);
    }

    /**
     * Returns the expression for the generalized transition graph <CODE>automaton</CODE>
     * with two states, a unique initial and unique final state. Evaluates to
     * the expression r = (r(ii)*r(ij)r(jj)*r(ji))*r(ii)*r(ij)r(jj)*. where
     * r(ij) represents the expression on the transition between state i (the
     * initial state) and state j (the final state)
     *
     * @param automaton
     *            the generalized transition graph with two states (a unique
     *            initial and final state).
     * @return the expression for the generalized transition graph <CODE>automaton</CODE>
     *         with two states, a unique initial and unique final state
     */
public static String getExpressionFromGTG(Automaton automaton) {
        String ii = getII(automaton);
        String ij = getIJ(automaton);
        String jj = getJJ(automaton);
        String ji = getJI(automaton);

        return getFinalExpression(ii, ij, jj, ji);
    }

    /**
     * Returns the regular expression that represents <CODE>automaton</CODE>.
     *
     * @param automaton
     *            the automaton
     * @return the regular expression that represents <CODE>automaton</CODE>.
     */
public static String convertToRegularExpression(Automaton automaton) {
        if (!isConvertable(automaton))
            return null;
        convertToGTG(automaton);
        return getExpressionFromGTG(automaton);
    }

    /* the string for the empty set. */
    public static final String EMPTY = "\u00F8";

    /* the string for lambda. */
    public static final String LAMBDA_DISPLAY = "epsilon";

    public static final String LAMBDA = "";

    /* the string for the kleene star. */
    public static final String KLEENE_STAR = "*";

    /* the string for the or symbol. */
    public static final String OR = "+";

    /** right paren. */
    public static final String RIGHT_PAREN = ")";

    /** left paren. */
    public static final String LEFT_PAREN = "(";


}
